/**
 * 对长度为n的顺序表L,编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，
 * 该算法删除线性表中所有值为x的数据元素
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

typedef struct Arr {
    int data[MAXSIZE];
    int n;
} arr;

/**
 * 算法:
 * 删除线性表中所有值为x的数据元素
 */
void deleteX(arr *, int);

int main() {
    arr *L;
    L = (arr *) malloc(sizeof(arr));
    printf("请输入表元素个数：");
    scanf("%d", &L->n);
    printf("请输入元素值：");
    for (int i = 0; i < L->n; i++) {
        scanf("%d", &L->data[i]);
    }
    printf("请输入X值：");
    int x;
    scanf("%d", &x);
    printf("\n执行删除x的方法：");
    deleteX(L, x);
    for (int i = 0; i < L->n; i++) {
        printf("\n%d ", L->data[i]);
    }
    printf("\n--程序结束正常---");
    return 0;
}

//算法思想：
//第一步：从前往后扫描顺序表，用k纪录当前值为x的数据元素的个数
// 第二步：如果扫描的当前元素的值为x，则k++；如果扫描的当前元素的值不为x，则将此当前元素向前移动k位
void deleteX(arr *L, int x) {
    int k = 0;
    for (int i = 0; i < L->n; i++) {
        if (L->data[i] == x) {
            k++;
        } else {
            L->data[i - k] = L->data[i];
        }
    }
    L->n = L->n - k;
}

//运行结果:
//5
//1
//2
//3
//4
//5
//3
//请输入表元素个数：请输入元素值：请输入X值：
//执行删除x的方法：
//1
//2
//4
//5 haha
//Process finished with exit code 0
